{ Siberian Olympiad. 2 stage.
  Problemset: http://agul-problems1.googlecode.com/svn/trunk/2010-2011/wso/stage2/wso_2stage.pdf
  Problem 6.
  Points: 100
}
{$APPTYPE CONSOLE}
uses SysUtils;
const besk=100000;
var x:array[1..105,1..105] of integer; n,m,i,j,a,b,c,k:longint;
function min(a,b:int64):int64;
begin
if a<b then result:=a else result:=b;
end;
procedure swap(var a,b:int64);
var i:int64;
begin
i:=a;
a:=b;
b:=i;
end;

begin
reset(input,'input.txt');
rewrite(output,'output.txt');
readln(n,m);
for i:=1 to n do begin
  for j:=1 to n do begin
    if i=j then x[i,j]:=0 else x[i,j]:=besk;
  end;
end;
for i:=1 to m do begin
  readln(a,b,c);
  x[a,b]:=min(x[a,b],c);
end;
for k:=1 to n do begin
  for i:=1 to n do begin
    for j:=1 to n do begin
      if (x[i,k]<besk) and (x[k,j]<besk) then x[i,j]:=min(x[i,j],x[i,k]+x[k,j]);
    end;
  end;
end;
for i:=1 to n do begin
  for j:=1 to n do begin
    if (x[i,j]>=besk) then write('Z ') else write(x[i,j],' ');
  end;
  writeln;
end;
end.

